"""
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，
每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
"""
# # 递归
# def cow_number(n):
#     if n<=4:
#         return n
#     else:
#         return cow_number(n-1) + cow_number(n-3)
#
# while True:
#     n = int(input())
#     if n == 0:
#         break
#     elif 0<n<55:
#         print(cow_number(n))
#     else:
#         print("num is 1到55")

# 代码优化 记忆型迭代

# def cow_population_memo(n, memo={}):
#     # 检查是否已经计算过
#     if n in memo:
#         return memo[n]
#         # 基本情况
#     if n == 1:
#         memo[n] = 1
#     elif n == 2:
#         memo[n] = 2
#     elif n == 3:
#         memo[n] = 3
#         # 递归情况
#     else:
#         memo[n] = cow_population_memo(n - 1, memo) + cow_population_memo(n - 3, memo)
#     return memo[n]
#
#
# # 测试
# n = 1000000
# print(f"第{n}年的时候共有{cow_population_memo(n)}头母牛")

#
# from functools import lru_cache
#
# @lru_cache(maxsize=None)
# def count_cows_memo(n):
#     if n <= 0:
#         return 0
#     elif n == 1 or n == 2 or n == 3:
#         return n
#     else:
#         return count_cows_memo(n - 1) + count_cows_memo(n - 3)
#
# # 测试代码
# year = int(input("请输入年份n："))
# print(f"在第{year}年，共有{count_cows_memo(year)}头母牛。")

#
# def count_cows_optimized(n):
#     if n <= 0:
#         return 0
#     elif n <= 3:
#         return n
#     else:
#         a, b, c = 1, 2, 3
#         for i in range(4, n + 1):
#             a, b, c = b, c, a + b
#         return c
#
# # 测试代码
# year = int(input("请输入年份n："))
# print(f"在第{year}年，共有{count_cows_optimized(year)}头母牛。")
#

import sys

def count_cows_optimized(n):
    if n <= 0:
        return 0
    elif n <= 3:
        return n
    else:
        a, b, c = 1, 2, 3
        for i in range(4, n + 1):
            a, b, c = b, c, a + b
        return c

# 增加整数到字符串转换的限制
sys.set_int_max_str_digits(10000)  # 增加转换大小

# 测试代码
year = int(input("请输入年份n："))
cows = count_cows_optimized(year)
print(f"在第{year}年，共有{cows}头母牛。")
